#pragma once

#include "iostream"
#include "vector"
#include "algorithm"

using namespace std;
/*HJJ QQ479287006
 *按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

 

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/n-queens
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释：如上图所示，4 皇后问题存在两个不同的解法。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/n-queens
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * */

vector<vector<string>> ret;
vector<string> temp;

//是否可以被放
bool isUsed(int row, int col, int n) {

    int trow = row;
    int tcol = col;

    //检测本位置 以及斜边 以及竖着的 以及横着的 是否被占用
    //heng方向
    for (int i = 0; i < n; ++i) {
        if (temp[row][i] == 'Q')
            return true;
    }
    //lie
    for (int i = 0; i < n; ++i) {
        if (temp[i][col] == 'Q')
            return true;
    }

    //斜边
    //先减到

    //从当前位置 斜上
    while (trow >= 0 && tcol >= 0) {
        if (temp[trow--][tcol--] == 'Q')
            return true;
    }

    tcol = col;
    trow = row;
    //向右下
    while (trow < n && tcol < n) {
        if (temp[trow++][tcol++] == 'Q')
            return true;
    }
    tcol = col;
    trow = row;
    //右上 row--； col++
    while (trow >= 0 && tcol < n) {
        if (temp[trow--][tcol++] == 'Q')
            return true;
    }
    tcol = col;
    trow = row;
    //左下 col-- row++
    while (trow < n && tcol >= 0) {
        if (temp[trow++][tcol--] == 'Q')
            return true;
    }


    return false;
}


void solveNQueensBACK(int n, int size, int nrow) {
    if (size > n)
        return;
    if (size == n) {
        ret.push_back(temp);
        return;
    }
    //todo 原来我这里写了俩for 超时了
    for (int j = 0; j < n; ++j) {
        if (isUsed(nrow, j, n))
            continue;
        temp[nrow][j] = 'Q';
        solveNQueensBACK(n, size + 1, nrow + 1);
        temp[nrow][j] = '.';
    }
}
vector<vector<string>> solveNQueens(int n) {
    string s = "";
    for (int i = 0; i < n; ++i) {
        s.push_back('.');
    }
    //初始化矩阵 为 .
    for (int i = 0; i < n; ++i) {
        temp.push_back(s);
    }
    solveNQueensBACK(n, 0, 0);
    return ret;
}